package top.minuy.subject.leetcode._20;


import java.util.Stack;

/**
 * 使用栈完成
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 * <p>
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 * <p>
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 * <p>
 * 输入：s = "{[]}"
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Minuy
 * @time 1:12
 * @date 2021/8/24
 */
public class Solution {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        // 依次遍历字符串中的字符
        for (int i = 0; i < s.length(); i++) {
            char tag = s.charAt(i);

            if (tag == '(' || tag == '[' || tag == '{') {
                // 判断是为左括号则入栈
                stack.push(tag);
            } else {
                // 否则看是否匹配

                // 栈为空说明没有左括号就来了右括号，不符合规则，失败
                if(stack.isEmpty()){
                    return false;
                }

                // 取出栈顶元素，上面判断了不为空，所以没异常
                char top = stack.pop();

                // 判断栈顶元素是否与目标元素是匹配的，不匹配可以直接返回假了
                if (top == '(' && tag!=')'){
                    return false;
                }else if (top == '[' && tag!=']'){
                    return false;
                }else if (top == '{' && tag!='}'){
                    return false;
                }
            }
        }
        // 最后判断是否还有多的没有匹配的，可以直接返回结果
        return stack.isEmpty();
    }
}
